#include <cstdio>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "SkipList.H"

/* Precondition : Sl non initialisee
 * Postcondition : Sl initialisee avec une cellule bidon*/
void Initialisation(SListe & Sl)
{
  int i = 0;
  int pile = 1; //est egal soit a 0 soit a 1
  SCellule * bidon = new SCellule;
	
  Sl.niveaux = 0;
	
  //On determine aleatoirement le nombre de niveaux
  srand(time(NULL));
  while(pile != 0 && Sl.niveaux < LEVELMAX)
    {
      Sl.niveaux++;
      pile = rand()%2;
    }
  //on initialise les pointeurs de la cellule bidon a NULL
  for(i=0;i<Sl.niveaux;i++)
    {
      bidon->suivant[i] = NULL;
    }
	
  Sl.ad = bidon;
}

SCellule * RechercheElementSListe(const SListe & Sl,Element e,int (*p_comp_elt)(Element,Element))
{
  int i = Sl.niveaux - 1;
  SCellule * tmp = Sl.ad;
	
  while(i >= 0 && tmp != NULL)
    {
      if(tmp->suivant[i] == NULL)
  	{
  	  i--;
  	}
      else if(p_comp_elt(e,tmp->suivant[i]->info) < 0)
  	{
  	  i--;
  	}
      else
  	{
  	  tmp = tmp->suivant[i];
	  i = tmp->niveau - 1;
  	}
    }
	
  return tmp;
}

void AjoutSListe(SListe & Sl,Element e,void (*p_init_elt)(Element &,Element))
{
  int pile = 1; //est egal soit a 0 soit a 1
  int niveaux = 0; //niveau de la cellule ajoutée
	
  //1) On cree la nouvelle cellule
  SCellule * sc = new SCellule;
  
  Element e1;
  p_init_elt(e1,e);
	
  sc->info = e1;
	
  //On determine aleatoirement le nombre de niveaux de la nouvelle cellule
	
  while(pile != 0 && niveaux < LEVELMAX)
    {
      niveaux++;
      pile = rand()%2;
    }
  //Mise a jour de la cellule bidon si Sl.niveaux < niveaux
  if(niveaux > Sl.niveaux)
    {
      while(Sl.niveaux != niveaux)
	{
	  Sl.ad->suivant[Sl.niveaux] = NULL;
	  Sl.niveaux++;
	}
    }
	
  //2) On ajoute la cellule
	
  int i = Sl.niveaux - 1; //compteur de niveaux
  int j = 0;
  int indice_tab = 0;
  SCellule * tmp;
  //SCellule* p;
  SCellule * tab[1000]; //remplacer par tab dyn
  tmp = Sl.ad;
  
  sc->niveau = niveaux;

  //on stoke et on met a jour les pointeurs
  while(i >= 0)
    {     
      if(tmp->suivant[i] == NULL)
      	{	
      	  if(i <= niveaux-1)
      	    {
      	      tab[indice_tab] = tmp->suivant[i]; //avec tab = tmp->s
      	      tmp->suivant[i] = sc;
      	      indice_tab++;
      	      i--;
      	    }

      	  else
      	    {
      	      i--;
      	    }
      	}

      else if(tmp->suivant[i] != NULL && plusPetitIntervalle(e, tmp->suivant[i]->info) == true)
      	{	
      	  if(i <= niveaux-1)
      	    {
      	      tab[indice_tab] = tmp->suivant[i]; 
      	      indice_tab++;
      	      tmp->suivant[i] = sc;
      	      i--;
      	    }
      	  else
      	    {
      	      i--;
      	    }
      	}

      else
      	{
      	  tmp = tmp->suivant[i];
	  i = tmp->niveau;
      	}
    }

  //On met en place dans la nouvelle cellule les pointeurs
  while(indice_tab-1 >= 0)
    {
      sc->suivant[indice_tab-1] = tab[j];
      j++;
      indice_tab--;
    }
  
}

//nv : niveau 0 correspond a afficher toute la liste 
//precondition : nv < Sl.niveaux
void AfficheSListe(const SListe & Sl,void (*p_affichage_elt)(Element))
{

  SCellule* tmp;
  int i = 0;
  
  tmp = Sl.ad->suivant[0];
  
  while (tmp != NULL)
    {
      printf("[%p] ", (void*)tmp);
      p_affichage_elt(tmp->info);
      printf(" ");
      
      for (i = 0; i < tmp->niveau; i++)
	{
	  printf("%p ", (void*)tmp->suivant[i]);
	}
      
      printf("\n");
      tmp = tmp->suivant[0];
    }

}

void SuppElementSListe(SListe & Sl,Element e,int (*p_comp_elt)(Element,Element),void (*p_supp_elt)(Element &))
{
  int i = Sl.niveaux - 1;
  SCellule * tmp = Sl.ad;
	
  SCellule * sup = RechercheElementSListe(Sl,e,p_comp_elt);
  //sup = sup->suivant[0];
  
  if (tmp->suivant[0] == NULL)
    {
      printf("La skip-list est vide. Retour au menu.\n\n");
      return;
    }
  
  if (egalIntervalle(sup->info, e))
    {
      while (tmp != NULL)
	{
	  while (i >= 0)
	    {
	      if (tmp->suivant[i] == sup)
		{
		  tmp->suivant[i] = sup->suivant[i];
		}
	      i--;
	    }
	  
	  tmp = tmp->suivant[0];

	  if(tmp != NULL)
	    {
	      i = tmp->niveau;
	    }
	}
  
      p_supp_elt(sup->info);
      delete sup;
    }
  
  else
    {
      printf("Intervalle introuvable. Retour au menu.\n\n");
    }
}

/* Precondition : Sl initialisee
 * Postcondition : Sl ne peut plus etre utilisee*/
void Testament(SListe & Sl,void (*p_supp_elt)(Element &))
{
  SCellule * tmp = Sl.ad;
  Sl.ad = Sl.ad->suivant[0];
  delete tmp;
  tmp = Sl.ad;
	
  while(tmp != NULL)
    {
      Sl.ad = Sl.ad->suivant[0];
      p_supp_elt(tmp->info);
		
      delete tmp;
      tmp = Sl.ad;
    }
	
  Sl.ad = NULL;
  Sl.niveaux = 0;
}

void CouvertureIntervalSListe (SListe& Sl, float f)
{
  SCellule * courante, *tmp = Sl.ad;
  Intervalle * inter;
  int i;
  
  i = Sl.niveaux - 1;
  
  if (tmp->suivant[0] == NULL)
  {
      printf("La skip-list est vide. Retour au menu.\n\n");
      return;
  }
  

    while (i >= 0)
    {
        courante = tmp->suivant[i];
        
	  if (courante != NULL)
	  {
	        inter = (Intervalle*) courante->info;
	        
	        if (inter->inf <= f && inter->sup >= f) {
	            break;
	        } else if (inter->sup < f) {
		        tmp = courante;
		        i = tmp->niveau - 1;
	        } else {
	            i--;
	        }
	  } else {
	    i--;
	  }
	
   }
  
  if (i >= 0 && courante != NULL)
    {
      printf("Le reel: %f, est dans l'intervalle: ", f); afficherIntervalle(courante->info);
    }

  else
    {
      printf("Le reel n'est pas dans un intervalle de la skip-list. Retour au menu\n\n");
    }
}
